import java.util.*;

public class project {
    public int longestPalindromeSubseq(String s) {
        int len=s.length();
        int[][] dp=new int[len][len];
        for(int i=len-1;i>=0;i--){
            dp[i][i]=1;
            for(int j=i+1;j<len;j++){
                if(s.charAt(i)==s.charAt(j)){
                    dp[i][j]=dp[i+1][j-1]+2;
                }else{
                    dp[i][j]=Math.max(dp[i+1][j],dp[i][j-1]);
                }
            }
        }
        return dp[0][len-1];
    }




















    public List<List<String>> solveNQueens(int n) {
        int[] arr=new int[n];
        List<List<String>> lists=new ArrayList<>();
        dfs(0,n,arr,lists);
        return lists;
    }

    private void dfs(int index, int n, int[] arr, List<List<String>> lists) {
        if(index==n){
            List<String> list=new ArrayList<>();
            for(int i=0;i<n;i++){
                char[] value=new char[n];
                Arrays.fill(value,'.');
                value[arr[i]]='Q';
                list.add(new String(value));
            }
            lists.add(list);
            return;
        }
        for(int i=0;i<n;i++){
            arr[index]=i;
            boolean flag=true;
            for(int j=0;j<index;j++){
                if(arr[index]==arr[j]||Math.abs(index-j)==Math.abs(arr[index]-arr[j])){
                    flag=false;
                    break;
                }
            }
            if(!flag){
                continue;
            }
            dfs(index+1,n,arr,lists);
        }
    }


















    public List<List<String>> solveNQueens1(int n) {
        int[] arr=new int[n];
        List<List<String>> list=new ArrayList<>();
        dfs1(0,n,arr,list);
        return list;
    }
    public void dfs1(int index,int len,int[] arr,List<List<String>> lists){
        if(index==len){
            List<String> list=new ArrayList<>();
            for(int i=0;i<len;i++){
                char[] value=new char[len];
                Arrays.fill(value,'.');
                value[arr[i]]='Q';
                list.add(new String(value));
            }
            lists.add(list);
            return;
        }
        for(int i=0;i<len;i++){
            arr[index]=i;
            boolean flag=true;
            for(int j=0;j<index;j++){
                if(arr[index]==arr[j]||Math.abs(index-j)==Math.abs(arr[index]-arr[j])){
                    flag=false;
                    break;
                }
            }
            if(!flag){
                continue;
            }
            dfs1(index+1,len,arr,lists);
        }
    }
























    public String removeDigit(String number, char digit) {
        int len=number.length();
        int index=0;
        for(int i=0;i<len;i++){
            if(number.charAt(i)==digit){
                index=i;
                if(i==len-1||number.charAt(i+1)>number.charAt(i)){
                    return number.substring(0,i)+number.substring(i+1,len);
                }
            }
        }
        return number.substring(0,index)+number.substring(index+1,len);
    }






















    public boolean isValid(String code) {
        int len=code.length();
        int index=0;
        Deque<String> deque=new ArrayDeque<>();
        while (index<len){
            char ch=code.charAt(index);
            if(ch=='<'){
                if(index==len-1){
                    return false;
                }
                if(code.charAt(index+1)=='/'){
                    int j=code.indexOf('>',index);
                    if(j<0){
                        return false;
                    }
                    String sub=code.substring(index+2,j);
                    if(deque.isEmpty()||!deque.peek().equals(sub)){
                        return false;
                    }
                    deque.pop();
                    index=j+1;
                    if(index!=len&&deque.isEmpty()){
                        return false;
                    }
                }else if(code.charAt(index+1)=='!'){
                    if(deque.isEmpty()){
                        return false;
                    }
                    if(index+9>len){
                        return false;
                    }
                    String sub=code.substring(index+2,index+9);
                    if(!"[CDATA[".equals(sub)){
                        return false;
                    }
                    int j=code.indexOf("]]>",index);
                    if(j<0){
                        return false;
                    }
                    index=j+1;
                }else{
                    int j=code.indexOf(">",index);
                    if(j<0){
                        return false;
                    }
                    String sub=code.substring(index+1,j);
                    if(sub.length()<1||sub.length()>9){
                        return false;
                    }
                    for(int i=0;i<sub.length();i++){
                        if(sub.charAt(i)<'A'||sub.charAt(i)>'Z'){
                            return false;
                        }
                    }
                    deque.push(sub);
                    index=j+1;
                }
            }else{
                if(deque.isEmpty()){
                    return false;
                }
                index++;
            }
        }
        return deque.isEmpty();
    }
}
